#include "tools.cpp"
class Solution {
  public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder, inorder, 0, 0, inorder.size());
    }

    TreeNode* buildTree(const vector<int>& pre, const vector<int>& in, int pre_start,
                        int in_start, int len) {
        if (len <= 0) return nullptr;
        auto root = new TreeNode(pre[pre_start]);
        int i = in_start;
        while (in[i] != root->val) ++i;
        int left_len = i - in_start;
        int right_len = len - left_len - 1;
        root->left = buildTree(pre, in, pre_start + 1, in_start, left_len);
        root->right = buildTree(pre, in, pre_start + left_len + 1,
                                in_start + left_len + 1, right_len);

        return root;
    }
};

int main() {
    std::vector<int> pre{3, 9, 20, 15, 7};
    std::vector<int> in{9, 3, 15, 20, 7};
    Solution s;
    s.buildTree(pre, in);
}
